4.1 二叉树

二叉树在实际应用中是离不开的，在很多底层实现上都会使用到二叉树，通过二叉树而扩展出来的结构也比较多。

本节我们将介绍二叉树的基本概念以及Go语言的基本实现，后续章节我们将继续讲解衍生出的二叉搜索树、平衡树。

本节代码存放目录为 lesson6

概念及原理

二叉树是一种非常重要的树形数据结构，它的每个节点最多有两个子节点，分别是左子节点和右子节点。

二叉树的结构非常适合用于组织层次化的数据，我们可以按照部门组织架构的方式去理解。

简单理解，二叉树其实就是一个倒过来的大树，只不过这棵树的每次分叉只有两个树枝分出去。

二叉树的结构示意图如下所示：

        1
       / \
      2   3
     / \   \
    4   5   6

• 节点 1 是根节点。

• 节点 2 和 节点 3 是节点 1 的左、右子节点。

• 节点 4、5、6 是叶节点，因为它们没有子节点。

从上面的结构我们可以看出，二叉树就是将大树倒过来，从唯一的一个根发散出来一棵树的形状。

在二叉树中我们会遇到下面这些术语，理解它们对于我们后续章节有帮助：

• 根节点：二叉树的最顶端节点，也就是上文中的1。

• 子节点：某个节点的左、右节点称为它的子节点，比如上文中的2、3。

• 父节点：某个节点直接指向的节点称为它的父节点，比如上文中的1就是2、3的父节点。

• 叶节点：没有子节点的节点称为叶节点，比如上文中的4、5、6。

• 树的高度：从根节点到最深叶节点的最长路径的长度称为树的高度，比如上文中树的高度为2，也就是1 -> 2、2 -> 4算出来就是2。

二叉树的结构是通用的，只不过不同的二叉树规则有一些不一样，对于二叉树其特性如下所示：

• 每个节点最多有两个子节点：左子节点和右子节点。

• 递归性质：二叉树是递归定义的，每个子节点本身也是一棵二叉树。

• 平衡性：如果左右子树的高度差不超过1，称为平衡二叉树，不同类型的二叉树有不同的平衡条件。

二叉树有几种分类，这些分类在我们进行一些算法构建时会使用到。二叉树的分类如下所示：

• 满二叉树：每一个非叶子节点都有两个子节点，且所有叶子节点位于同一层。

          1
         / \
        2   3
       / \ / \
      4  5 6  7
  

• 完全二叉树：除了最后一层外，每一层的节点都是满的，且最后一层的叶子节点靠左对齐。

  下面的示例中，第一层第二层都是没有缺的，同时最后一层的4、5、6都是靠左对齐，所以是满足完全二叉树的，如果6是靠右的，那么就不满足了。

          1
         / \
        2   3
       / \ /
      4  5 6
  

• 二叉搜索树（BST）：左子节点的值小于父节点的值，右子节点的值大于父节点的值，在之后我们会进行详细讲解。

二叉树的遍历是访问每个节点的过程，我们以上文的结构进行说明：

        1
       / \
      2   3
     / \   \
    4   5   6

常见的遍历方式如下所示：

• 前序遍历：先访问根节点，再访问左子树，最后访问右子树。

  • 顺序：根 -> 左 -> 右，即：1 -> 2 -> 4 -> 5 -> 3 -> 6

• 中序遍历：先访问左子树，再访问根节点，最后访问右子树。

  • 顺序：左 -> 根 -> 右，即：4 -> 2 -> 5 -> 1 -> 3 -> 6

• 后序遍历：先访问左子树，再访问右子树，最后访问根节点。

  • 顺序：左 -> 右 -> 根，即：4 -> 5 -> 2 -> 6 -> 3 -> 1

• 层序遍历：按层次从上到下逐层遍历树的节点.

  • 即：1 -> 2 -> 3 -> 4 -> 5 -> 6

Go语言的实现

Go语言实现二叉树与之前我们进行链表实现大致方法差不多，在具体规则上有一些差别。

实现二叉树首先我们需要定义一个规则，在本实例中我们定义：奇数都存储在左节点中，偶数都存储在有节点中。

我们最终实现的结构是这样的：

         1
       /   \
      3     2
     / \   / \
    5   7 6   4

实现代码如下所示：

// Tree 定义二叉树结构
type Tree struct {
    // 数据
    data int
    // 左节点
    left *Tree
    // 右节点
    right *Tree
}

func (t *Tree) insert(data int) {
    newTree := &Tree{
        data: data,
    }

    // 奇数处理
    if data%2 != 0 {
        if t.left == nil {
            t.left = newTree
            return
        }

        if t.right == nil {
            t.right = newTree
            return
        }

        t.left.insert(data)
        return
    }

    // 偶数处理
    if t.right == nil {
        t.right = newTree
        return
    }

    if t.left == nil {
        t.left = newTree
        return
    }
    t.right.insert(data)
}

func (t *Tree) printTree() {
    if t == nil {
        return
    }
    if t.left != nil {
        fmt.Printf("%d, ", t.left.data)
    }
    if t.right != nil {
        fmt.Printf("%d\n", t.right.data)
    }
    if t.left == nil && t.right == nil {
        return
    }
    t.left.printTree()
    t.right.printTree()
}

func main() {
    tree := &Tree{
        data: 1,
    }
    tree.insert(2)
    tree.insert(3)
    tree.insert(4)
    tree.insert(5)
    tree.insert(6)
    tree.insert(7)
    tree.printTree()
}

结果输出如下所示：

3, 2
5, 7
6, 4

二叉树的实现其实与双向链表的实现差不多，双向链表具备前后指针，而二叉树则是具备左右指针。

通过左右指针的控制最终绘制为一个树形结构，在Go语言中其实如果只是应用层面的话我们使用二叉树不是太多，但是我们还是可以做一个掌握。

这一章学习完成之后，您可能还不是太了解。在后续章节中我们将继续讲解比较有应用意义的二叉搜索树、红黑树等知识。